package leetcode.editor.cn;

//[122]买卖股票的最佳时机 II
public class BestTimeToBuyAndSellStockIi122 {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockIi122().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //找到右边大的值，就可以买卖.无数次
        public int maxProfitFindRightMax(int[] prices) {
            if (prices == null || prices.length < 1) return 0;
            int fit = 0;
            int preDay = prices[0];
            for (int i = 1; i < prices.length; i++) {
                preDay = prices[i - 1];
                int curDay = prices[i];
                if (curDay > preDay) {
                    fit += curDay - preDay;
                }
            }
            return fit;
        }


        //dp
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length < 1) return 0;
            int len = prices.length;
            //int [][][] dp = new int[len][len][2];
            // k 无穷大。所以可以忽略，这个纬度。一直允许交易。
            int [][] dp = new int[len][2];
            dp[0][1] = -prices[0];//first day buy.
            dp[0][0] = 0;

            for (int i = 1; i < len; i++) {
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i-1][0] - prices[i],dp[i-1][1]);
            }
            return dp[len-1][0];
        }

        //dp 空间优化
        public int maxProfit_int(int[] prices) {
            if (prices == null || prices.length < 1) return 0;
            int len = prices.length;
            //int [][][] dp = new int[len][len][2];
            // k 无穷大。所以可以忽略，这个纬度。一直允许交易。
            //int [][] dp = new int[len][2];
            int dp_0_1 = -prices[0];//first day buy.
            int dp_0_0 = 0;

            for (int i = 1; i < len; i++) {
                int temp = dp_0_0;
                dp_0_0 = Math.max( dp_0_0, dp_0_1 + prices[i]);
                dp_0_1 = Math.max(temp - prices[i],dp_0_1);
            }
            return dp_0_0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}